package LeetCode;

public class LC_685_RedundantConnectionII {

    public static void main(String[] args) {

    }

    class Solution {
        public int[] findRedundantDirectedConnection(int[][] edges) {
            int[] in = new int[edges.length + 4];
            boolean has2parent = false;
            int[] has2parentPos = new int[2];
            for (int i = 0; i < edges.length; i++) {
                int[] t = edges[i];
                in[t[1]]++;
                if (in[t[1]] == 2) {
                    has2parent = true;
                    has2parentPos[1] = i;
                    for (int j = 0; j < i; j++)
                        if (edges[j][1] == t[1]) {
                            has2parentPos[0] = j;
                            break;
                        }
                    break;
                }
            }
            int[] ret = findRedundantConnection(edges, -1);
            if (!has2parent) return ret;
            if (ret == null) return edges[has2parentPos[1]];
            if (findRedundantConnection(edges, has2parentPos[0]) == null)
                return edges[has2parentPos[0]];
            else
                return edges[has2parentPos[1]];
        }

        int[] findRedundantConnection(int[][] edges, int p) {
            int[] root = new int[edges.length + 4];
            for (int i = 0; i < root.length; i++) root[i] = i;
            for (int q = 0; q < edges.length; q++) {
                if (p == q) continue;
                int i = edges[q][0], j = edges[q][1];
                for (int k = 0; k < root.length; k++) {
                    if (root[k] == j)
                        root[k] = root[i];
                }
                if (root[i] == j) return edges[q];
            }
            return null;
        }
    }

}